<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var detectCycle = function (head) {
        // 方法一：采用map---时间：O（n）（）---空间：O（n）（）
        const map = new Map();
        while (head) {
          if (map.has(head)) {
            return head;
          }
          map.set(head, true);
          head = head.next;
        }
        return null

        // 方法二：快慢指针---时间：O（2n）（两次遍历）---空间：O（1）（两个指针）
        // ---------------错误写法（因为你不能确定快慢指针相交的节点就是起点，比如[3,2,0,-4]的测试用例，起点是2，但是快慢指针相交的点是-4）
        // let fast = head
        // let slow = head
        // while(fast && fast.next){
        //   slow = slow.next
        //   fast = fast.next.next
        //   if(fast===slow){
        //     return slow
        //   }
        // }
        // return null
        // ---------------正确写法
        // （假设slow走k到相遇点，fast就是走了2k到相遇点，多余的k就是在环里面转圈，k是环长的整数倍；
        // 假设相遇点到环起点的距离为m，环的起点到头节点的距离就为k-m；
        // 从相遇点前进k-m也恰好到达环起点,因为 fast 指针，从相遇点开始走k步(k是环长的整数倍)可以转回到相遇点，那走 k - m 步肯定就走到环起点了）
        // （看图片解析https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/）
        // let fast = head;
        // let slow = head;
        // while (fast && fast.next) {
        // // 必须放前面，不然就是一直相等
        //   slow = slow.next;
        //   fast = fast.next.next;
        //   if (fast === slow) {
        //     break;
        //   }
        // }
        // // 没有环
        // if (!fast || !fast.next) {
        //   return null;
        // }
        // slow = head;
        // while (true) {
        //   if (fast === slow) {
        //     return slow;
        //   }
        //   slow = slow.next;
        //   fast = fast.next;
        // }
      };
    </script>
  </body>
</html>
